package 字节;

import java.util.Arrays;

/*
分治 时间复杂度最好最坏都是log(n log n )
空间复杂度为log(log n)
 */
public class 归并排序 {
    public static void main(String[] args) {
        int[] arr={9,6,4,2,6,4,1};
        int[] res=sort(arr);
        for(int i:res){
            System.out.printf(i+" ");
        }
    }

    static int[] sort(int[] nums){
        if(nums.length<2) return nums;
        int mid=nums.length/2;
        int[] left= Arrays.copyOfRange(nums,0,mid);
        int[] right=Arrays.copyOfRange(nums,mid,nums.length);
        return merge(sort(left),sort(right));
    }

    static int[] merge(int[] left,int[] right){
        int[] res=new int[left.length+right.length];
        int i=0;
        int a=0;
        int b=0;
        while (a<left.length&&b<right.length){
            if(left[a]<=right[b]){
                res[i++]=left[a++];

            }else {
                res[i++]=right[b++];

            }
        }
        while (a<left.length){
            res[i++]=left[a++];
        }
        while (b<right.length){
            res[i++]=right[b++];
        }
        return res;
     }
}
